package graph;

import linearlist.Queue;

/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/30 :12:04
 * @Description
 */
class BreadFirstSearchTest{
    public static void main(String[] args) {
        Graph graph = new Graph(13);
        graph.addEdge(0,5);
        graph.addEdge(0,1);
        graph.addEdge(0,2);
        graph.addEdge(0,6);
        graph.addEdge(5,3);
        graph.addEdge(3,4);
        graph.addEdge(4,6);

        graph.addEdge(7,8);

        graph.addEdge(9,11);
        graph.addEdge(9,10);
        graph.addEdge(9,12);
        graph.addEdge(11,12);

        BreadFirstSearch firstSearch = new BreadFirstSearch(graph,0);

        System.out.println("测试与某个顶点统统的顶点数量："+firstSearch.count());
        System.out.println("判断0与4是否相通："+firstSearch.marked(4));
        System.out.println("判断0与7是否相通："+firstSearch.marked(7));
    }
}
public class BreadFirstSearch {
    //用来存储待搜索领接表的点
    private Queue<Integer> waitSearch;
    //记录有多少个顶点与s顶点相遇
    private int count;
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点
   public  BreadFirstSearch(Graph graph,int s){
    this.count = 0;
    this.waitSearch = new Queue<Integer>();
    this.marked = new boolean[graph.v()];
    bfs(graph,s);
    }
    //使用广度优先搜索找出G图中v顶点的所有相邻顶点
    private  void bfs(Graph graph,int v){
       //把当前顶点v标识为已搜索
        marked[v] = true;
        //让顶点v进入队列，待搜索
        waitSearch.enqueue(v);
        //通过循环，如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
        while (!waitSearch.isEmpty()){
            //弹出一个待搜索的顶点
            Integer wait = waitSearch.dequeue();
            //遍历wait顶点的邻接表
            for (Integer integer : graph.adj(wait)) {
                if (!marked(integer)){
                    bfs(graph,integer);
                }
            }
//让相通的顶点加一
            count++;
        }
    }
    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
       return this.marked[w];
    }
    //获取与顶点s相通的所有顶点的总数
    public int count(){
       return count;
    }
}
